package q871_minRefuelStops;

import java.util.PriorityQueue;

public class Solution_2 {
    /*
    贪心的做法
    我们使用一个优先队列来解决加油
    首先使用一个curr来记录我们这次要到达的位置的里程 一共有n个加油站和一个终点 = n + 1
    那么为了到达该位置需要耗油 curr - prev 其中prev记录了上次我们所到达的位置
    此时维护一个优先队列 队列中记录了我们到达该位置前所有加油站能够加油的量的 排序 （从大到小）
    为了实现最小次数加油 可以采用如下方式：
    每次加入一个新的加油量时 队列对其进行排序 而我们当前要到达的位置计算过fuel之后
    如果出现fuel 小于 0 ，意味着我们需要进行加油 此时我们从队列中能提供最大加油量的站开始
    将油量加入到fuel中 直到fuel > 0 （如果队列空了但仍然小于0 就意味着不能够到达）
    这样做就使得我们能够每次都从最大加油值取 满足最小加油次数的条件
     */
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
        int ans = 0, prev = 0, fuel = startFuel;
        int n = stations.length;
        for (int i = 0; i <= n; i++) {
            int curr = i < n ? stations[i][0] : target;
            fuel -= curr - prev;
            // 题目中给了startFuel至少为1的条件 否则需要进行额外判断 例如初始时是否有油
            while (fuel < 0 && !pq.isEmpty()) {
                fuel += pq.poll();
                ans++;
            }
            if (fuel < 0) {
                return -1;
            }
            if (i < n) {
                pq.offer(stations[i][1]);
                prev = curr;
            }
        }
        return ans;
    }
}
